package leetcode.primary;

public class T44 {
    public boolean isMatch(String s, String p) {

        char[] ss = (" "+s).toCharArray();
        char[] pp = (" "+p).toCharArray();
        int lens = ss.length;
        int lenp = pp.length;
        int[][] dp = new int[lenp][lens];
        dp[0][0] = 1;
        for (int i = 1; i < lenp; i++) {
            for (int j = 0; j < lens; j++) {
                if (pp[i]=='*'){
                    if (dp[i-1][j]==1){
                        for (;j<lens;j++){
                            dp[i][j]=1;
                        }
                    }
                }else {
                    if (j>=1 && dp[i-1][j-1]==1 && (ss[j]==pp[i] || pp[i]=='?')){
                        dp[i][j]=1;
                    }
                }
            }
        }

        for (int i = 0; i < ss.length; i++) {
            System.out.print(ss[i]+" ");
        }
        System.out.println();
        for (int i = 0; i < pp.length; i++) {
            System.out.print(pp[i]+" ");
        }
        System.out.println();
        for (int i =0;i<lenp;i++){
            for (int j =0;j<lens;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(dp[lenp-1][lens-1] == 1);
        return dp[lenp-1][lens-1] == 1;
    }

    public static void main(String[] args) {
        T44 test = new T44();
        boolean ans = test.isMatch("aa", "a");
        System.out.println(ans);
    }
}
